'''
https://leetcode.cn/problems/sort-list/submissions/207254474/
'''
from typing import Optional

from c03_list.utils import ListNode


class Solution:
    def sortList_forceSolution(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        cur = head
        t = []
        while cur:
            t.append(cur)
            cur = cur.next
        t.sort(key = lambda x: x.val)
        for i in range(1, len(t)):
            t[i-1].next = t[i]
        t[-1].next = None
        return t[0]

    '''
    @see c04_sort/merge_sort.merge_sort2
    循环版本的归并排序
    '''
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 先不写了，太麻烦了
        pass